package _07剪邮票.拓展_连通性检测;

import java.util.Arrays;

/**
 在快速查找算法中，只需经过一个连接就可以找到节点；
 而在快速合并中中，可能需要多个节点才能找到。

 例三：快速合并的加权版本
 */
public class demo3 {

    public static void main(String[] args) {
        int N = 10;
        int id [] = new int[N];
        int sz [] = new int[N];
        for(int i = 0; i < N; i++){
            id[i] = i;
            sz[i] = 1;
        }
        int [] [] a =  new int [][]{
                {3,4},{4,9},{8,0},{2,3},{5,6},{2,9},
                {5,9},{7,3},{4,8},{5,6},{0,2},{6,1}
        };
        System.out.println(Arrays.toString(id));
        for(int [] s : a){
            int i, j, p = s[0], q = s[1];
            for(i = p; i != id[i]; i = id[i]);
            for(j = q; j != id[j]; j = id[j]);
            if(i == j){
                continue;
            }
            if(sz[i] < sz[j]){
                id[i] = j;
                sz[j] += sz[i];
            }else{
                id[j] = i;
                sz[i] += sz[j];
            }
            System.out.println(" " + p + " " + q);
            System.out.println(Arrays.toString(id));
            System.out.println(Arrays.toString(sz));
        }
    }
}